In recent years, studies on an ad hoc network in which a plurality of communication devices (hereinafter, referred to as node devices) are connected to each other in an autonomously distributed manner have been advanced. The respective node devices in the ad hoc network autonomously build a network in accordance with a communication environment.
For example, when a node device in the ad hoc network communicates with a node device in a network different from the ad hoc network, communication has to be established via a gateway device capable of connecting both the networks.
In such a case, each node device in the ad hoc network transmits a data frame to a target gateway device by causing an adjacent node device to relay the data frame received from another adjacent node device (hereinafter, referred to as an adjacent node device) based on a network topology (routing table). At this time, each node device selects a path with higher transmission quality and transmits the data frame (see Japanese Laid-open Patent Publication No. 2009-081854, for example).
The routing table is built by exchanging hello frames and is updated such that an optimal path may be selected. Each entry in the routing table includes a value indicating frequency in use, and the value indicating the frequency in use is reset when the path indicated by the entry is used. In addition, the value indicating the frequency in use is “0” when the path indicated by the entry is not used for a predetermined period of time, which is a state indicating that the path is not used.
In order to suppress consumption of memory, the number of entries in the routing table is typically limited. When the number of entries of gateway devices has reached the upper limit thereof, the entry whose value indicating the frequency in use is “0” is to be replaced in the related art.
That is, it is not possible to register a gateway device with higher path quality in the routing table in a case where there is no entry whose value indicating the frequency in use is “0” in a state where the number of entries of the gateway devices has reached the upper limit thereof even if a gateway device with higher path quality is added to the network.
In particular, since the value indicating frequency in use included in an entry is often reset in a node device which is used as a path to a plurality of gateway devices, it is difficult to replace entries in the routing table. For this reason, it is not possible to build an optimal path.